/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class AddOneRowtoTree {
	  public class TreeNode {
		      int val;
		      TreeNode left;
		      TreeNode right;
		      TreeNode(int x) { val = x; }
		  }
    public TreeNode addOneRow(TreeNode root, int v, int d) {
        if(d==1){
        	TreeNode newNode=new TreeNode(v);
        	newNode.left=root;
        	return newNode;
        }
        if(root==null){
        	return null;
        }
        if(d==2){
        	TreeNode newNode1=new TreeNode(v);
        	TreeNode newNode2=new TreeNode(v);
        	newNode1.left=root.left;
        	newNode2.right=root.right;
        	root.left=newNode1;
        	root.right=newNode2;
        	return root;
        }
        root.left=addOneRow(root.left, v, d-1);
        root.right=addOneRow(root.right, v, d-1);
        return root;
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
